package com.wj.graph;

/**
 * dfs:深度优先搜索
 * @author wen.jie
 * @date 2021/8/27 11:08
 */
public class DepthFirstSearch {
    //索引代表顶点，值代表当前顶点是否已经被搜索
    private boolean[] marked;
    //记录有多少顶点与s顶点相通
    private int count;

    public DepthFirstSearch(Graph G, int s) {
        this.marked = new boolean[G.V()];
        dfs(G, s);
    }

    //深度优先搜索找出G图中v顶点的所有相通顶点
    private void dfs(Graph G, int v) {
        //标为已搜索
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (!marked(w))
                dfs(G, w);
        }
        count++;
    }

    //判断w顶点与s顶点是否相通
    public boolean marked(int w){
        return marked[w];
    }

    //获取与顶点s相通的所有顶点的总数
    public int count() {
        return this.count;
    }
}
